package com.leetcode.p400;

import com.bean.TreeNode;
import com.utils.TreeUtils;

public class Test450 {

    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) {
            return null;
        }

        if (root.val < key) {
            root.right = deleteNode(root.right, key);
        } else if (root.val > key) {
            root.left = deleteNode(root.left, key);
        } else {
            if (root.left == null) {
                return root.right;
            } else if (root.right == null) {
                return root.left;
            }

            TreeNode node = root.right;

            while (node.left != null) {
                node = node.left;
            }

            node.left = root.left;
            root = root.right;
        }

        return root;
    }

    public static void main(String[] args) {
        TreeNode root = TreeUtils.buildTree4();
        TreeUtils.showTree(root);

        Test450 test = new Test450();
        TreeNode result = test.deleteNode(root, 15);

        TreeUtils.showTree(result);
    }

}
